/**
 * @file   Student.h
 * @author li_zhiqi <3180103041@zju.edu.cn>
 * @date   Fri Oct  2 10:15:01 2020
 * 
 * @brief  a student information management system and
 *         a sorting system by merging and heap
 * 
 */

#ifndef __STUDENT__
#define __STUDENT__
#include <limits>
#include <cstdlib>
#include <iostream>

class Student{
private:
  int std_no;/**<Student number, every student has a unique ID number. */
  char major;/**<Student major marked by one character, M for math, P for 
                 Physics, C for Chemistry. */
  double GPA;/**<GPA range: 0 ~ 5 */
public:
  /** 
   * Default constructor
   * 
   */
  Student();
  /** 
   * Constructor,get student ID, major and GPA.
   * 
   * @param std_nodata studenr ID
   * @param majordata major, M for Math, P for Physics, C for Chemistry.
   * @param GPAdata GPA,range 0 ~ 5.
   */
  Student(int std_nodata,char majordata, double GPAdata);
  /** 
   * get the major of the student.
   * 
   * 
   * @return the major of the student
   */
  char get_major();
  /** 
   * get GPA of the student.
   * 
   * 
   * @return GPA of the student
   */
  double get_GPA();
  /** 
   * print out the ID, major and GPA of the student
   * 
   * 
   * @return Error code, 0 for OK.
   */
  int printout();  
};
class Heap{
private:
  Student *data;    /**< data of heap */
  int length;   /**< number of the elements of heap */
public:
#define PARENT(i) ((((i) + 1) >> 1) - 1)
#define LEFTCHILD(i) (((i + 1) << 1) - 1)
#define RIGHTCHILD(i) ((i + 1) << 1)
  /** 
   * Default constructor.
   * 
   */
  Heap();
  /** 
   * Constructor,initialize data with a bunch of student element pointed by heapdata.
   * 
   * @param heapdata Pointer to the elements data.
   * @param length Total number of the element data.
   */
  Heap(Student *heapdata, int l);
  /** 
   * Default destructor.
   * 
   */
  ~Heap();
  /** 
   * Get the length of the heap.
   * 
   * 
   * @return the length of the heap
   */
  int get_length();
  /** 
   * Shift down the i-th node to recover the properties of max-heap.
   * 
   * @param i the index of the broken node
   * 
   * @return Error code, 0 for OK.
   */
  int shiftdown(int i);

  /** 
   * Sort all the elements by heapsort method.
   * 
   * 
   * @return Error code, 0 for OK. 
   */
  int heapsort();
  /** 
   * Write the elements in the Heap to Student class array A.
   *  
   * @param A array to be written
   * 
   * @return Error code, 0 for OK.
   */
  int write_Student(Student *A);
};

  /** 
   * Sort students by major with heap-sort method.
   * 
   * @param A pointer to elements of student information
   * @param n length Total number of the element data.
   * 
   * @return Error code, 0 for OK.
   */
   int sort_m(Student *A,int n);

  /** 
   * Sort students by GPA after sort_m, with merge_sort method.
   * 
   * @param A pointer to elements of student information
   * @param n length Total number of the element data.
   * 
   * @return Error code, 0 for OK.
   */
   int arrange(Student *A,int n);

  /** 
   * Merge two sorted array parts to a sorted one.
   * 
   * @param data array to be sorted with two sorted parts
   * @param p the start index for the first sorted part
   * @param q the last index for the second sorted part
   * @param r the last index for the first part
   * 
   * @return Error code, 0 for OK.
   */
   int Merge(Student *A, int p, int q, int r);
  /** 
   * Apply MergeSort by Divide-and-Conquer strategy.
   * 
   * @param data array to be sorted
   * @param p the start index of array
   * @param q the last index of array
   * 
   * @return Error code, 0 for OK.
   */
   int MergeSort(Student *A, int p, int q);

#else
//do nothing
#endif
